/**
 * 
 */
package leetCode;

/**
 * @author zhong
 *
 */
public class DistributeCoinsinBinaryTree {
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	public int distributeCoins(TreeNode root) {
		return helper(root)[0];
	}

	private int[] helper(TreeNode root) {
		if (root == null) {
			return new int[4];
		}
		int[] res = new int[3];
		int[] left = helper(root.left);
		int[] right = helper(root.right);
		res[0] = Math.abs(left[0]) + Math.abs(right[0]) + Math.abs(left[1]) + Math.abs(right[1]);
		res[2] = left[2] + right[2] + root.val;
		res[3] = left[3] + right[3] + 1;
		res[1] = res[3] - res[2];
		return res;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
